package com.datastructure.test.generateallofchildrenserial;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class GenerateAllOfChildrenSerial {

    public StringBuilder stringBuilder;
    public static void main(String[] args) {
        GenerateAllOfChildrenSerial generateAllOfChildrenSerial = new GenerateAllOfChildrenSerial();
        String[] generatePermutation = generateAllOfChildrenSerial.generatePermutation("aba");
        System.out.println(generatePermutation);
    }

    public String[] generatePermutation (String s) {
        // write code here
        char[] chars = s.toCharArray();
        LinkedList<Character> linkedList = new LinkedList<>();
        Set<String> set = new HashSet<>();
        dfs(0,chars,linkedList,set);
        return set.toArray(new String[0]);
    }

    private void dfs(int start, char[] chars, LinkedList<Character> linkedList, Set<String> set) {
        stringBuilder=new StringBuilder();
        for (Character character : linkedList) {
            stringBuilder.append(character);
        }
        set.add(stringBuilder.toString());
        for(int i = start;i<chars.length;i++){
            if(i>start&&chars[i]==chars[i-1]){
                continue;
            }
            linkedList.add(chars[i]);
            dfs(i+1,chars,linkedList,set);
            linkedList.removeLast();
        }
    }

    public String[] generatePermutation1 (String s) {
        // write code here
        char[] ch = s.toCharArray();
//        ArrayList<String> ans = new ArrayList<>();
        HashSet<String> ans = new HashSet<>();
        process(ch, 0 , ans, "");
        String[] res = ans.toArray(new String[0]);
        return res;
    }

    public static void process(char[] ch, int index, HashSet<String> ans, String path){
        if (index == ch.length){
            ans.add(path);
            return;
        }
        String no = path;
        process(ch,index + 1, ans, no);
        String yes = path + ch[index];
        process(ch,index + 1, ans, yes);
    }
}
